Shevchenko đã chơi 111 trận và ghi 48 bàn thắng cho đội tuyển Ukraina, trong đó có kỳ World Cup 2006 và Euro 2012. Anh ghi bàn thắng quốc tế đầu tiên cho mình vào tháng 5 năm 1996, trong 1 trận giao hữu với Thổ Nhĩ Kỳ.

Vào tháng 3 năm 2000, Người quản lý của câu lạc bộ Dynamo là Valeri Lobanovsky trở thành huấn luyện viên trưởng của đội tuyển Ukraina, trong nhiệm vụ đưa đội này tham dự vòng chung kết World Cup 2002. Shevchenko ghi 10 bàn trong vòng loại, nhưng Ukraina sau đó đã bị loại tại trận đấu quyết định với Tuyển Đức. Anh ghi một trong 5 bàn của tuyển Ukraina tại vòng loại Euro 2008. Tại Euro 2012 được đồng tổ chức tại quê nhà Ukraina (cùng với Ba Lan), anh ghi được cả hai bàn thắng trong khuôn khổ lượt trận đầu tiên của bảng D với Thụy Điển. Tuy nhiên đội tuyển Ukraina phải dừng bước ở vòng bảng sau khi để thua Pháp với tỉ số 0-2 và thua Anh với tỉ số 0-1 (trong trận đấu này, bàn thắng của Marko Dević có đi qua vạch vôi rõ ràng của đội tuyển Anh nhưng trọng tài Viktor Kassai không công nhận bàn thắng hợp lệ này).